package com.nan.leetcode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Test3 {

    //给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    public boolean isValid(String s) {
//需要使用栈来完成
        //首先需要创建一个栈，
        Stack<Character> stack=new Stack<>();
        //遍历字符串
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);//返回字符串s的i位置，用字符c接收
            //遇到左括号，就需要入栈
            if(c=='('||c=='{'||c=='['){
                stack.push(c);//c入栈
                continue;
            }
            //右括号的情况
            //取栈顶元素和当前括号进行匹配
            if(stack.isEmpty()){
                return false;
            }
            Character top=stack.pop();//取到栈顶元素，对空栈进行peek会直接抛出异常
            //pop是出栈，peek是取栈顶元素
            if(top=='('&&c==')'){
                continue;
            }
            if(top=='['&&c==']'){
                continue;
            }
            if(top=='{'&&c=='}'){
                continue;
            }
            //如果没有触发到上面的三种合法情况，直接返回false
            return false;
        }
        //循环结束，说明字符串遍历完成，还需要判断一下，栈是否为空
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }


    //请你仅使用两个队列实现一个后入先出（LIFO）的栈，
    // 并支持普通栈的全部四种操作（push、top、pop 和 empty）。
    class MyStack {
        private Queue<Integer> A=new LinkedList<>();
        private Queue<Integer> B=new LinkedList<>();

        public MyStack() {

        }

        public void push(int x) {
            //入栈的时候，直接往A中插入
            A.offer(x);
        }

        public int pop() {
            //出栈的时候，把A中元素往B中倒腾，当A中只剩一个元素的时候，
            // 最后这个元素就是要被删除的元素
            if(A.isEmpty()&&B.isEmpty()){
                return 0;
            }
            while(A.size()>1){
                int tmp=A.poll();//将A队列中的元素出队列
                B.offer(tmp);//再将这个元素放入B队列中。
            }
            //当上面的循环结束，A中就只剩一个元素了，
            // 就将最后这个元素作为出栈的结果即可
            int ret=A.poll();
            swapAB();
            return ret;
            //最终完成操作之后，要交换A和B的身份
        }
        private void swapAB(){
            Queue<Integer> tmp=A;
            A=B;
            B=tmp;
        }

        public int top() {
            if(A.isEmpty()&&B.isEmpty()){
                return 0;
            }
            while(A.size()>1){
                int tmp=A.poll();//将A队列中的元素出队列
                B.offer(tmp);//再将这个元素放入B队列中。
            }
            int ret=A.poll();
            B.offer(ret);//这个操作是和pop唯一区别
            swapAB();
            return ret;
        }

        public boolean empty() {
            return A.isEmpty()&&B.isEmpty();
        }
    }


    //请你仅使用两个栈实现先入先出队列。
    // 队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
    static class MyQueue {
        Stack<Integer> A= new Stack<>();
        Stack<Integer> B=new Stack<>();
        public MyQueue() {

        }

        public void push(int x) {
            //入栈的时候，需要先把B中的元素倒进A中，再进行入栈
            while (!B.isEmpty()){//当B不为空的时候
                int tmp=B.pop();
                A.push(tmp);
            }
            A.push(x);
        }

        public int pop() {
            if(A.isEmpty()&&B.isEmpty()){
                return 0;
            }
//            //把A中元素倒入B中，剩下的最后一个元素就是出栈的元素
//            while(A.size()>1){
//               int tmp= A.pop();
//               B.push(tmp);
//            }
//            int ret=A.pop();//此时取到A的最后一个元素
            while (!A.isEmpty()){
                int tmp=A.pop();
                B.push(tmp);
            }
            return B.pop();
        }

        public int peek() {
            if(A.isEmpty()&&B.isEmpty()){
                return 0;
            }
//            while (A.size()>1){
//                int tmp=A.pop();
//                B.push(tmp);
//            }
//            int ret=A.pop();//最后这个元素还得再放入B中
//            B.push(ret);
            while (!A.isEmpty()){
                int tmp=A.pop();
                B.push(tmp);
            }
            return B.peek();
        }

        public boolean empty() {
            return A.isEmpty()&&B.isEmpty();
        }
    }
    public static void main1(String[] args) {
        MyQueue myQueue=new MyQueue();
        myQueue.push(1);
        myQueue.push(2);
        int ret=myQueue.peek();
        System.out.println("ret="+ret);
        ret= myQueue.pop();
        System.out.println("ret="+ret);
        boolean isEmpty=myQueue.empty();
        System.out.println(isEmpty);
    }
    //设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    static class MinStack {
        Stack<Integer> A=new Stack<>();
        Stack<Integer> B=new Stack<>();//B中保存的就是当前A的最小值
        public MinStack() {

        }

        public void push(int val) {
            //先把val放入A中
            A.push(val);
            //比较val和B的栈顶的值
            if(B.isEmpty()){
                B.push(val);
                return;
            }
            int min=B.peek();
            if (val<min){
                min=val;
            }
            B.push(min);
        }

        public void pop() {
            if(A.isEmpty()){
                return;
            }
            A.pop();
            B.pop();
        }

        public int top() {
            if(A.isEmpty()){
                return 0;
            }
            return A.peek();
        }

        public int getMin() {
            if(B.isEmpty()){
                return 0;
            }
            return B.peek();
        }
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        minStack.getMin();
        minStack.pop();
        minStack.top();
        minStack.getMin();
    }
}

